package org.aplombh.java.leetcode.all;

import java.util.ArrayList;
import java.util.List;

public class _22括号生成 {
}

class Solution22_1 {
    public List<String> generateParenthesis(int n) {

        List<String> ans = new ArrayList<>();
        if (n == 1){
            ans.add("()");
        }
        else {
            for (String s : generateParenthesis(n - 1)) {
                for (int i = 0; i < s.length()+1; i++) {
                    String tmp = s.substring(0, i) + "()" + s.substring(i);
                    if (!ans.contains(tmp))
                        ans.add(tmp);
                }
            }
        }
        return ans;
    }
}